//先对数组进行随机洗牌
//然后再进行快速排序，也就是先用第一个数作为基准数，之后这个数左边的数都是比他小的数，右边的数都是比他大的数
//递归对被分开的两边再进行上面同样的排序就完成了快速排序
//大概思路就是从两端对数组进行遍历，然后左边找比基准数大的，右边找比基准数小的，两边都找到后交换
//最后的结果是右边的j在左边的i左边了，然后那个时候直接交换j对应的数和基准数就OK
//当然别忘了这是个递归程序，记得返回最后基准数组所在的位置，方便递归调用来排序两边
//比归并排序还快
//最好情况的时间复杂度是nlogn，最坏情况是二次的
//不稳定
//和归并排序一样，也可以将小于几的数组用插入排序排，节约时间和空间
//还有就是可以采样几个数（中间和两端），然后将大小处于中间的数作为基准数
public class QuickSort extends InsertionSort{
    public void MySort(int data[])
    {
       Shuffle shuffle=new Shuffle();
       shuffle.shuffle(data);
       Sort(data,0,data.length-1);
    }

    public void Sort(int data[],int left,int right)
    {
       int i=left,j=right;
       //当数组较小的时候采用插入排序
       if(right-left<=5)
       {
        super.MySort_p(data,left,right);
        return ;
       }

       //采样找到中间数作为基准数

       while(true)
       {
        while(data[i]<=data[left])   //i的职责是找到比基准数要大的，所以小于的时候继续循环  i最后停的位置就是比基准数大的那个数的位置
        {
          if(i>j)
          {
            break;
          }
          i++;
        }
        while(data[j]>data[left])   //思路类上  不管比较结果如何，j--一定会执行 j最后停的位置是比基准数小的或者一样的那个数的位置
        {
          if(j<i)
          {
            break;
          }
          j--;
        }
        if(i<j)
        {
            Exchange(data,i,j); 
            i++;
            j--;
        }
        else
        {
            break;
        }
       }
       Exchange(data,left,j);
       Sort(data,left,j-1);
       Sort(data,j+1,right);
    }
}
